package LearnAlgorithm.c_递归and查找排序;

import java.util.Scanner;

/*
公司现在要对几万员工的年龄进行排序,
因为公司员工的人数非常多,所以要求排序算法的效率要非常高
输入:输入可能包含多个测试样例,对于每个测试案例,
-输入的第一行为一个整数n(1<=n<=1000000):
	代表公司内员工的人数。
-输入的第二行包括n个整数:
	代表公司内每个员工的年龄。其中，员工年龄age的取值范围为(1<=age<=99)
-输出:
	对应每个测试案例,请输出排序后的n个员工的年龄,每个年龄后面有一个空格
 */
public class s对所有员工年龄排序 {
	public static int[] helper = new int[100];
	public static int[] helper2 = null;
	public static void main(String[] args) {
		Input();
	}
	
	public static void Input() {
		Scanner scanner = new Scanner(System.in);
		System.out.println("请输入员工数N：");
		int N = scanner.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			System.out.println("请输入第" + (i + 1) + "个员工的年龄");
			arr[i] = scanner.nextInt();
		}
		System.out.println("全部年龄录入完毕");
		countSort(arr, helper);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	/**
	 * 人类年龄的计数排序不用考虑负数
	 * 所以用仅能解决重复元素的计数排序就足够了
	 * @param arr
	 * @param helper
	 */
	public static void countSort(int[] arr, int[] helper) {
		int current = 0;
		for (int i = 0; i < arr.length; i++) {
			helper[arr[i]]++;
		}
		for (int i = 1; i < helper.length; i++) {//年龄一定大于1；从i = 1开始
			while (helper[i] > 0) {
				arr[current++] = i;
				helper[i]--;
			}
		}
	}
	
	/**
	 * 自己练手再写一遍能解决负数的计数排序
	 * @param arr
	 * @param helper
	 */
	public static void countSortPlus(int[] arr, int[] helper) {
		int current = 0;
		int min = arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] < min) {
				min = arr[i];
			}
		}
		int max = arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		helper = new int[max + 1 - min];
		for (int i = 0; i < arr.length; i++) {
			helper[arr[i] - min]++;
		}
		for (int i = 0; i < helper.length; i++) {
			while (helper[i] > 0) {
				arr[current++] = i + min;//偏移量加回来
				helper[i]--;
			}
		}
	}
}
